package LC;

import java.math.BigInteger;

/**
 * https://leetcode.com/problems/multiply-strings/description/
 * Given two non-negative integers num1 and num2 represented as strings,
 * return the product of num1 and num2.
 * Note:
 * The length of both num1 and num2 is < 110.
 * Both num1 and num2 contains only digits 0-9.
 * Both num1 and num2 does not contain any leading zero.
 * You must not use any built-in BigInteger library
 * or convert the inputs to integer directly.
 */
public class LC_043_MultiplyStrings_JavaAPI_Math {
    public static void main(String[] args) {
        String s1 = "123";
        String s2 = "3";
        String res1 = Solution_1.multiply(s1, s2);
        String res2 = Solution_2.multiply(s1, s2);
        System.out.println(res1);
        System.out.println(res2);
    }

    static class Solution_1 {
        static String multiply(String num1, String num2) {
            return new BigInteger(num1).multiply(new BigInteger(num2)).toString();
        }
    }

    static class Solution_2 {
        static String multiply(String num1, String num2) {
            num1 = new StringBuilder(num1).reverse().toString();
            num2 = new StringBuilder(num2).reverse().toString();

            int[] b = new int[num1.length() + num2.length()];
            for (int i = 0; i < num1.length(); i++)
                for (int j = 0; j < num2.length(); j++)
                    b[i + j] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');

            for (int i = 0; i < num1.length() + num2.length(); i++) {
                if (b[i] > 9) {
                    b[i + 1] += b[i] / 10;
                    b[i] %= 10;
                }
            }

            StringBuilder stringBuilder = new StringBuilder();
            for (int i = num1.length() + num2.length() - 1; i >= 0; i--)
                stringBuilder.append(b[i]);
            while (stringBuilder.charAt(0) == '0' && stringBuilder.length() > 1)
                stringBuilder.deleteCharAt(0);

            return stringBuilder.toString();
        }
    }
}
